//给定一个非空特殊的二叉树，每个节点都是正数，并且每个节点的子节点数量只能为 2 或 0。如果一个节点有两个子节点的话，那么该节点的值等于两个子节点中较小的一
//个。 
//
// 更正式地说，root.val = min(root.left.val, root.right.val) 总成立。 
//
// 给出这样的一个二叉树，你需要输出所有节点中的第二小的值。如果第二小的值不存在的话，输出 -1 。 
//
// 
//
// 示例 1： 
//
// 
//输入：root = [2,2,5,null,null,5,7]
//输出：5
//解释：最小的值是 2 ，第二小的值是 5 。
// 
//
// 示例 2： 
//
// 
//输入：root = [2,2,2]
//输出：-1
//解释：最小的值是 2, 但是不存在第二小的值。
// 
//
// 
//
// 提示： 
//
// 
// 树中节点数目在范围 [1, 25] 内 
// 1 <= Node.val <= 231 - 1 
// 对于树中每个节点 root.val == min(root.left.val, root.right.val) 
// 
// Related Topics 树 深度优先搜索 二叉树 
// 👍 154 👎 0
#include <iostream>

using namespace std;

//leetcode submit region begin(Prohibit modification and deletion)

 //Definition for a binary tree node.
 struct TreeNode {
     int val;
     TreeNode *left;
     TreeNode *right;
     TreeNode() : val(0), left(nullptr), right(nullptr) {}
     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 };

class Solution {
public:
    int findSecondMinimumValue(TreeNode* root) {
        if(!root || !root->left || !root->right) return -1;

        int left = root->left->val,right = root->right->val;
        //根结点与左节点值相同 找 左子树
        if (root->val == root->left->val){
            left = findSecondMinimumValue(root->left);
        }

        //根结点与右节点值相同 找 右子树
        if (root->val == root->left->val){
            right = findSecondMinimumValue(root->right);
        }

        //若根结点等于左右子树的第二小节点
        if (root->val == left && root->val == right){
            return -1;
        }
        return root->val < min(left,right) ? min(left,right) : max(left,right);
    }
};
//leetcode submit region end(Prohibit modification and deletion)
